package leetcode

import (
	"sort"
)

// 试着打印所有组合
func dfsInput(nums []int) [][]int {
	sort.Ints(nums)
	res := make([][]int, 0)

	for i := 0; i < len(nums); i++ {
		dfs(nums, i, []int{}, &res)
	}

	return res
}

func dfs(nums []int, idx int, c []int, res *[][]int) {
	if idx == len(nums) {
		return
	}
	c = append(c, nums[idx])
	*res = append(*res, c)
	dfs(nums, idx+1, c, res)
	//c = c[:len(c)-1]
}

func QuicktSort(nums []int, n int) {
	quicktSort(nums, 0, n-1)
}

func quicktSort(nums []int, l, r int) {
	if l >= r {
		return
	}
	q := quickPatition(nums, l, r)
	quicktSort(nums, l, q-1)
	quicktSort(nums, q+1, r)
}

func quickPatition(nums []int, l, r int) int {
	privot := nums[r]
	i := l
	for j := i; j < r; j++ {
		if nums[j] < privot {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
	}
	nums[i], nums[r] = nums[r], nums[i]
	return i
}
